/*
 * @lc app=leetcode.cn id=90 lang=cpp
 *
 * [90] 子集 II
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        for (auto num : nums){
            numHash[num] += 1;
        }

        auto numInfoIter = numHash.begin();

        buildSubset(numInfoIter);

        return result;
    }
private:
    // <num, duplicated times>
    std::map<int, int> numHash;
    std::vector<int> candidate;
    vector<vector<int>> result;
private:
    void buildSubset(std::map<int, int>::iterator& numInfoIter){
        bool finished = false;
        if (numInfoIter == std::prev(numHash.end())){
            // std::next will not get map.end()
            // so check std::prev(numHash.end()) here
            finished = true;
        }

        int currentNum = numInfoIter->first;
        int currentNumCounter = numInfoIter->second;

        for (int i=0;i<=currentNumCounter;++i){
            // push i num
            for (int j=0;j<i;j++){
                candidate.push_back(currentNum);
            }
            numInfoIter = std::next(numInfoIter);

            if (finished){
                result.emplace_back(candidate);
            }else{
                buildSubset(numInfoIter);
            }

            // pop i num
            for (int j=0;j<i;j++){
                candidate.pop_back();
            }
            numInfoIter = std::prev(numInfoIter);
        }
    }
};
// @lc code=end

